In accordance with protocols of the Transmission Control Protocol/Internet Protocol (TCP/IP) family, each node of the network typically has a view of only a portion of the network, with the result that the routing function is distributed across the network without any of the nodes knowing the complete route taken by the data packets.
The routing protocol can be the Transmission Control Protocol (TCP) or the User Datagram Protocol (UDP), for example.
In most cases, these protocols are sufficient because the sender of a packet is generally interested only in the actual transmission of their packet, and not in the exact route that it takes. Nevertheless, there are a few applications in which a knowledge of the complete route taken by the packets is at least important, if not essential.
One such application is the broadcasting of packets to a plurality of destinations, for example, as shown in FIG. 1 and as described in Request for Comments (RFC) 1054, entitled “Host Extensions for IP Multicasting”.
FIG. 1 shows seven nodes R1, R2, R3, . . . , R7. The node R1 sends out data packets. The data packets typically form part of a data stream, for example a video data stream. Also shown in the figures are arrows corresponding to the directions in which information is communicated between the nodes. The double-headed arrows represent symmetrical communications.
The nodes R6 and R7 are to receive the data stream. They therefore send to the source R1 of the stream a registration message, for example a “Join” message of the Internet Group Management Protocol (IGMP) as defined in RFC 1112.
The registration message from the node R7 passes through the nodes R5 and R2 before reaching the source node R1. The registration message from the node R6 also passes through the nodes R4, R3, R2 and R1.
The data stream is therefore transmitted at the same time to the node R2 for transmission to the node R6 and to the node R5 for transmission to the node R5.
If the node R1 had known the exact route to each of the destination nodes, it would have transmitted a single data stream to the node R5, for the latter to duplicate that stream, both to the node R7 and to the node R6.
Thus a lack of knowledge of the complete route between the nodes rules out optimum use of the data network and overloads it unnecessarily.
One solution to knowing a route between two nodes is the “TraceRoute” software, the first versions of which date from 1988.
Its basic principle consists of setting an increasing time to live for a packet sent to the node to which a route is looked for. Each node passed through decrements the time to live of the packet by one unit. When the time to live reaches 0, the node that has received the packet no longer transmits it, but sends the sender a Time To Live Exceeded message, inserting its identifier into the message. Accordingly, a simple method used by the TraceRoute software consists of transmitting a packet with a time to live of 1, then 2, 3, etc. until the target node is finally reached. The complete route to the target node can be reconstructed by storing in memory each time the node sending the Time To Live Exceeded message.
However, a method of this kind has the major drawback of necessitating a large number of packets. In a real world data network, the size of the routes can be large and can therefore imply an excessive number of packets and Time To Live Exceeded messages.
A similar method is disclosed in U.S. Pat. No. 5,675,741, entitled “Method and apparatus for determining a communications route between two nodes in an Internet Protocol (IP) network”. This is also an iterative method. The number of packets transmitted is therefore proportional to the size of the route looked for. The method can therefore lead to congestion of the network because of the proliferation of these route tracing messages.